class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int target = 0;
        for(int i = 0 ; i < nums.size();i++)
        {
            target += nums[i];
        }
        if(target % 2 == 1) return false; //总和不能平分就直接false了
        target /=2; //因为只是求一半，所以就对半切了
        vector<int> dp(target+1,0);
        for(int i = 0; i < nums.size();i++)
        {
            for(int j = target;j >= nums[i];j--)
            {
                dp[j] = max(dp[j] , dp[j-nums[i]] + nums[i]);
            }
        }
        if(dp[target] == target)
            return true;
        return false;
    }
};

//二维数组写法
class Solution {
public:
	bool canPartition(vector<int>& nums) {
		int target = 0;
		for (int i = 0; i < nums.size(); i++)
		{
			target += nums[i];
		}
		if (target % 2 == 1) return false; //总和不能平分就直接false了
		target /= 2; //因为只是求一半，所以就对半切了
		vector<vector<int>> dp(nums.size(), vector<int>(target + 1, 0));
		for (int i = 1; i < nums.size(); i++)
		{
			for (int j = 1; j <= target; j++)
			{
				if (j < nums[i])
				{
					dp[i][j] = dp[i - 1][j];
				}
				else
				{
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
				}
			}
		}
		int a = dp[nums.size() - 1][target];
		if (dp[nums.size() - 1][target] == target)
			return true;
		return false;
	}
};